package com.captjack.other;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Jack Sparrow
 * @version 1.0.0
 * @date 2022/10/16 22:37
 * package com.captjack
 */
public class LruCache<K, V> {

    private final Map<K, LruNode<K, V>> map;

    private final int capacity;

    private transient final LruNode<K, V> head;

    private transient final LruNode<K, V> tail;

    public LruCache(int capacity) {
        map = new HashMap<>(capacity);
        this.capacity = capacity;
        this.head = new LruNode<>();
        this.tail = new LruNode<>();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    public V get(K key) {
        LruNode<K, V> lruNode = map.get(key);
        if (lruNode == null) {
            return null;
        }
        moveToHead(lruNode);
        return lruNode.value;
    }

    public void put(K key, V value) {
        LruNode<K, V> node = map.get(key);
        if (node == null) {
            // key不存在创建新节点
            LruNode<K, V> newNode = new LruNode<>(key, value);
            // put
            map.put(key, newNode);
            // 加到头部
            addToHead(newNode);
            // 清理最少使用数据
            if (map.size() > capacity) {
                LruNode<K, V> last = removeTail();
                map.remove(last.key);
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(LruNode<K, V> node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(LruNode<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(LruNode<K, V> node) {
        removeNode(node);
        addToHead(node);
    }

    private LruNode<K, V> removeTail() {
        LruNode<K, V> last = tail.prev;
        removeNode(last);
        return last;
    }

    private static class LruNode<K, V> {
        private K key;
        private V value;
        LruNode<K, V> prev;
        LruNode<K, V> next;

        public LruNode() {
        }

        public LruNode(K key, V value) {
            this.key = key;
            this.value = value;
        }

    }

}